⟸ Go Back ⟸

Exercise 8 (Homework 2).

(regular languages, minimization of DFAs)

On DFA minimization

1. A DFA with unreachable states cannot be minimum. What is the cost of determining whether a DFA has unreachable states?

2. What is the cost of Moore minimization algorithm (with a reasonable implementation)?

3. The minimum DFA recognizing a given language is unique up to isomorphism. What about NFAs? In particular, is an NFA of minimum size unique for a given language?